package code.classic150on2025;

import java.util.*;

public class TheBackTrace {
    // 52. N 皇后 II
    int total52 = 0;

    public int totalNQueens(int n) {
        backTrace52(n, 0, new boolean[n], new boolean[2 * n], new boolean[2 * n]);
        return total52;
    }

    private void backTrace52(int n, int now, boolean[] line, boolean[] bias1, boolean[] bias2) {
        if (now == n) {
            total52++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!line[i] && !bias1[now - i + n] && !bias2[now + i]) {
                line[i] = true;
                bias1[now - i + n] = true;
                bias2[now + i] = true;
                backTrace52(n, now + 1, line, bias1, bias2);
                line[i] = false;
                bias1[now - i + n] = false;
                bias2[now + i] = false;
            }
        }
    }

    // 17. 电话号码的字母组合
    public List<String> letterCombinations(String digits) {
        Map<Character, char[]> map = new HashMap<>();
        map.put('2', new char[]{'a', 'b', 'c'});
        map.put('3', new char[]{'d', 'e', 'f'});
        map.put('4', new char[]{'g', 'h', 'i'});
        map.put('5', new char[]{'j', 'k', 'l'});
        map.put('6', new char[]{'m', 'n', 'o'});
        map.put('7', new char[]{'p', 'q', 'r', 's'});
        map.put('8', new char[]{'t', 'u', 'v'});
        map.put('9', new char[]{'w', 'x', 'y', 'z'});
        List<String> list = new ArrayList<>();
        letterBackTrace(digits, 0, list, map, new StringBuilder());
        return list;
    }

    private void letterBackTrace(String digits, int index, List<String> list, Map<Character, char[]> map, StringBuilder sb) {
        if (index == digits.length()) {
            if (!digits.isEmpty())
                list.add(sb.toString());
            return;
        }
        char[] nowDial = map.get(digits.charAt(index));
        for (char c : nowDial) {
            sb.append(c);
            letterBackTrace(digits, index + 1, list, map, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    // 77. 组合
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> lists = new ArrayList<>();
        combineBackTrace(n, 1, k, 0, lists, new ArrayList<>());
        return lists;
    }

    private void combineBackTrace(int n, int now, int k, int count, List<List<Integer>> lists, List<Integer> list) {
        if (count == k) {
            lists.add(new ArrayList<>(list));
            return;
        }
        // 剪枝
        if (k - count > n - now + 1)
            return;
        for (int i = now; i <= n; i++) {
            list.add(i);
            combineBackTrace(n, i + 1, k, count + 1, lists, list);
            list.remove(list.size() - 1);
        }
    }

    // 46. 全排列
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        permuteBackTrace(nums, new boolean[nums.length], lists, new ArrayList<>());
        return lists;
    }

    private void permuteBackTrace(int[] nums, boolean[] visit, List<List<Integer>> lists, List<Integer> list) {
        if (list.size() == nums.length) {
            lists.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visit[i])
                continue;
            visit[i] = true;
            list.add(nums[i]);
            permuteBackTrace(nums, visit, lists, list);
            list.remove(list.size() - 1);
            visit[i] = false;
        }
    }

    // 39. 组合总和
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> lists = new ArrayList<>();
        combinationSumBackTrace(candidates, 0, target, 0, new ArrayList<>(), lists);
        return lists;
    }

    private void combinationSumBackTrace(int[] candidates, int index, int target, int now, List<Integer> list, List<List<Integer>> lists) {
        if (now > target)
            return;
        if (now == target) {
            lists.add(new ArrayList<>(list));
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            list.add(candidates[i]);
            now += candidates[i];
            combinationSumBackTrace(candidates, i, target, now, list, lists);
            now -= candidates[i];
            list.remove(list.size() - 1);
        }
    }

    // 22. 括号生成
    public List<String> generateParenthesis(int n) {
        List<String> stringList = new ArrayList<>();
        generateParenthesisBackTrace(n, 0, 0, stringList, new StringBuilder());
        return stringList;
    }

    private void generateParenthesisBackTrace(int n, int left, int right, List<String> stringList, StringBuilder sb) {
        if (left == n && right == n) {
            stringList.add(sb.toString());
            return;
        }
        if (left < n) {
            sb.append('(');
            generateParenthesisBackTrace(n, left + 1, right, stringList, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (right < n && left > right) {
            sb.append(')');
            generateParenthesisBackTrace(n, left, right + 1, stringList, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    // 79. 单词搜索
    public int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    boolean ans79 = false;

    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        boolean[][] visit = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                existBackTrace(board, word, i, j, 0, visit);
            }
        }
        return ans79;
    }

    private void existBackTrace(char[][] board, String word, int i, int j, int index, boolean[][] visit) {
        if (word.charAt(index) != board[i][j])
            return;
        if (index == word.length() - 1) {
            ans79 = true;
            return;
        }
        visit[i][j] = true;
        for (int[] dir : dirs) {
            int newI = i + dir[0], newJ = j + dir[1];
            if (newI < 0 || newI >= board.length || newJ < 0 || newJ >= board[0].length || visit[newI][newJ])
                continue;
            existBackTrace(board, word, newI, newJ, index + 1, visit);
        }
        visit[i][j] = false;
    }

    public static void main(String[] args) {
        TheBackTrace t = new TheBackTrace();
        t.exist(new char[][]{{'a'}}, "a");
    }
}
